class Solution
{
public:
    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        set<vector<int>> result;
        vector<int> cur;
        int n = candidates.size();
        function<void(int, int)> dfs = [&](int i, int sum)
        {
            if (sum > target || i >= n)
            {
                return;
            }
            if (sum == target)
            {
                result.insert(cur);
                return;
            }

            dfs(i + 1, sum);
            int num = candidates[i];

            cur.push_back(num);
            if (sum + num == target)
            {
                result.insert(cur);
            }
            else
            {
                dfs(i, sum + num);
                dfs(i + 1, sum + num);
            }
            cur.pop_back();
        };
        dfs(0, 0);
        return {result.begin(), result.end()};
    }
};